#include <omp.h>
#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <cmath>

using namespace std;

class MyStr {
	protected:
		string str;
		
	public:
		MyStr ( );
		MyStr ( char * ); 
		MyStr ( string );

		int length ( ) 			  { return str.length(); };
		char operator[] ( int i ) { return str[i]; };
		string operator() ( ) 	  { return str; };
};

MyStr::MyStr ( ) {
	return;
}

MyStr::MyStr ( char *s ) { 
	str = string( s ); 
}

MyStr::MyStr ( string s ) { 
	str = s; 
}

class Pattern: public MyStr {
	public:
		int *W;

		Pattern ( );
		Pattern ( char * ); 
		Pattern ( string );
};

Pattern::Pattern( ) {
	W = NULL;
}

Pattern::Pattern( char *s ) : MyStr( s ) { 
	unsigned int i;
	W = new int[str.length()];
	for (i = 0; i < str.length(); i++) W[i] = 1;
}

Pattern::Pattern( string s ) : MyStr( s ) { 
	unsigned int i;
	W = new int[str.length()];
	for (i = 0; i < str.length(); i++) W[i] = 1;
}


class Text: public MyStr {
	public:
		bool *M;
		int *J;
		int lenJ;

		Text ( ); 
		Text ( char * );
		Text ( string s );
		
		int Left ( int, int, Pattern& );
};

Text::Text( ) {
	M = NULL;
	J = NULL;
	lenJ = 0;
}

Text::Text( char * s ) : MyStr( s ) {
	M = new bool[str.length()];
	J = NULL;
	lenJ = 0;
}

Text::Text( string s ) : MyStr( s ) {
	M = new bool[str.length()];
	J = NULL;
	lenJ = 0;
}

int Text::Left ( int k, int a, Pattern& P ) {
	int j1, j2, w;
	char x, y, z;

	  // not terminating condition
	if (k != 0) {
		  // if 2^(k-1)*(2a+1) is beyond end of text
		if ( ((1<<(k-1))*(2*a+1)) >= length() ) 
			j1 = -1;
		else 
			j1 = Left( k-1, 2*a+1, P );

		j2 = Left( k-1, 2*a, P );

		  // no match in 2a+1, return 2a
		if (j1 == -1) return j2;

		  // no match in 2a, return 2a+1
		if (j2  == -1) return j1;

	} else {
		j1 = 2*a+1;
		j2 = 2*a;
	}

	  // matches in 2a and 2a+1 or at leaf
	w = P.W[j1 - j2 + 1];		// get witness
	x = P[w];					
	y = P[j1-j2+w];
	z = str[j1-1+w];

	if (z != y) M[j2] = false;	// j2 cannot be an occurrence
	if (z != x) M[j1] = false;	// j1 cannot be an occurrence

	  // only zero or one of the following can be true
	if (M[j2]) return j2;
	if (M[j1]) return j1;
	
	return -1;	// no potential match
}

inline void Error ( const char *msg ) {
	cout << "Error - " << msg << endl; 
	exit(1);
}

inline void Usage () { Error( "Usage oops!!" ); }

string ReadToEnd ( char *filename ) {
	ifstream inFile;
	string sFile, sBuf;

	inFile.open( filename );
	if (!inFile.is_open()) Error( "Cannot open file" );
	inFile.seekg( 0, ios::end );
	sFile.reserve( inFile.tellg() );
	inFile.seekg( 0, ios::beg );
	while (inFile.good()) {
		getline(inFile, sBuf);
		sFile += sBuf;
	   	if (!inFile.eof()) sFile += '\n';
	}
	inFile.close();

	return sFile;
}

void Step2 ( Pattern& P, Text& T ) {
	int i;
	int m = P.length();
	int n = T.length();
	int k = (int)log2(m);
	int a = ceil((n-m+1.0)/(1<<k));
	
	T.J = new int[a]; 
	T.lenJ = a;

	for (i = 0; i <= n - m; i++) T.M[i] = true;

	for (i = 0; i < a; i++)
		T.J[i] = T.Left( k, i, P );

}

bool MatchTest( int j, Pattern& P, Text& T ) {
	int i;

	for (i = j; i < P.length(); i++) if (T[i] != P[i-j]) return false;
	
	return true;
}

void Step3 ( Pattern& P, Text& T ) {
	int i;

	for (i = 0; i < T.lenJ; i++) 
		T.M[T.J[i]] = MatchTest( T.J[i], P, T );
}


int main ( int argc, char *argv[] ) {
	int i;
	Pattern P;
	Text T;

	  // Use OMP timing if available, otherwise c++ clock
	#ifdef _OPENMP
		double 	t1, t2;
	#else
		time_t	t1, t2;
	#endif

	#ifdef _OPENMP
		t1 = omp_get_wtime();
	#else
		t1 = time(0);
	#endif

	  // Verify, read, and output parameters
    for (i = 0; i < argc; i++) cout << argv[i] << " "; cout << endl;

    for (i = 1; i < argc-1; i+=2) {
        if (string(argv[i]) == "-p") 
			P = Pattern(argv[i+1]);
        else if (string(argv[i]) == "-t") 
			T = Text(argv[i+1]);
		else if (string(argv[i]) == "-pf") 
			P = Pattern( ReadToEnd( argv[i+1] ) );
		else if (string(argv[i]) == "-tf") 
			T = Text( ReadToEnd( argv[i+1] ) );
    } // for

    if (P.length() == 0 || T.length() == 0) Usage();
	
	cout << "Pattern = " << P();
	cout << "Text = " << T();

	Step2( P, T );
	Step3( P, T );

	  // Return duration
	#ifdef _OPENMP
		t2 = omp_get_wtime();
		cout << t2-t1 << endl;
	#else
		t2 = time(0);
		cout << difftime(t2, t1) << endl;
	#endif

	return 0;
} // main()
